
/*
* File: maze.c
* ------------
* This program solves a maze by recursive backtracking.
*/

#include <stdio.h>
#include "genlib.h"
#include "graphics.h"
#include "mazelib.h"
#include "simpio.h"

/*NUMMAXPOINTS is the maximum points in the 
* array that contains the path to the solution
* of the maze.*/
#define NUMMAXPOINTS 100

/* Private function prototypes */
static int SolveMaze(pointT pt, int *nRecurs);
static pointT AdjacentPoint(pointT pt, directionT dir);
static string choose(void);
static int FindPath(pointT pt, pointT path[], const int maxPathSize);
static void printGroupMembers();

/* Main program */

main(){

	
	string choice;
	int numRecursions = 0;

	InitGraphics();
	printGroupMembers();
	choice = choose();

	ReadMazeMap(choice);
	if (SolveMaze(GetStartPosition(), &numRecursions)) {
		printf("The marked squares show a solution path.\n");
		printf("Number of recursions: %d.\n", numRecursions);
	}
	else {
		printf("No solution exists.\n");
	}
}

/*
* Procedure: printGroupMembers
* Usage: printGroupMembers();
* --------------------------------
* This procedure prints the authors of this
* program to screen.
*/
static void printGroupMembers(){

	printf("This program was developed by: ");
	printf("Jim Glansk, S141587, ");
	printf("Henrik Wistbacka, S142066\n");
}


/*
* Function: SolveMaze
* Usage: if (SolveMaze(pt)) . . .
* -------------------------------
* This function attempts to generate a solution to the current
* maze from point pt.  SolveMaze returns TRUE if the maze has
* a solution and FALSE otherwise.  The implementation uses
* recursion to solve the submazes that result from marking the
* current square and moving one step along each open passage.
*/

static int SolveMaze(pointT pt, int *nRecurs)
{
	directionT dir;
	static pointT points[NUMMAXPOINTS];
	int length = 0;
	*nRecurs += 1;

	if (OutsideMaze(pt)) return (TRUE);
	if (IsMarked(pt)) return (FALSE);
	MarkSquare(pt);
	for (dir = North; dir <= West; dir++) {
		if (!WallExists(pt, dir)) {
			if (SolveMaze(AdjacentPoint(pt, dir), nRecurs)) {
				length = FindPath(pt, points, NUMMAXPOINTS);
				printf("Length of maze: %d.\n", length);
				return (TRUE);
			}
		}
	}

	return (FALSE);
}

/*
* Function: AdjacentPoint
* Usage: newpt = AdjacentPoint(pt, dir);
* --------------------------------------
* This function returns the pointT that results from moving
* one square from pt in the direction specified by dir.  For
* example, if pt is the point (1,1), AdjacentPoint(pt, East)
* would return the point (2,1).
*/

static pointT AdjacentPoint(pointT pt, directionT dir)
{
	pointT newpt;

	newpt = pt;
	switch (dir) {
	case North: newpt.y++; break;
	case East:  newpt.x++; break;
	case South: newpt.y--; break;
	case West:  newpt.x--; break;;
	}
	return (newpt);
}

/*
* Procedure: choose
* Usage: filename = choose();
* --------------------------------
* This function returns the name of the
* file the user chooses.
*/
static string choose(void){

	int choice;

	printf("Select one of the following maps:\n");
	printf("1. Pathlen.\n");
	printf("2. Example.\n");
	printf("3. Unmark.\n");

	while (TRUE){
		choice = GetInteger();
		if (choice < 1 || choice > 4){
			break;
		}

		switch (choice){
		case 1:
			return("pathlen.maz");
		case 2:
			return("example.maz");
		case 3:
			return("unmark.maz");
		default:
			printf("Please input valid map");
		}
	}
}

/*
* Function: FindPath
* Usage: length = FindPath(pt, path, maxPathSize);
* --------------------------------
* This procedure prints the coordinates of one 
* solution to the maze to screen. It also 
* returns the coordinates to one solution
* in path[]. Input is a point pt that belongs to
* the solution, an array path to store the coordinates
* and maxPathSize, which is the size of the array path.
* The length to one solution is returned in length.
* 
*/
static int FindPath(pointT pt, pointT path[], const int maxPathSize){

	pointT start = GetStartPosition();

	static int length = 0;
	static int index = 1;

	length++;

	if (pt.x == start.x && pt.y == start.y){
		int i;

		if (index <= maxPathSize)
			path[maxPathSize - (index)] = pt; 

		printf("The following path is a solution:\n");
		for (i = maxPathSize - index; i < maxPathSize; i++)
			printf("x: %-2d, y: %-2d\n", path[i].x, path[i].y);

		return length;
	}

	if (index <= maxPathSize) //Store the points from the end counting down to the
												//beginning.
		path[maxPathSize - (index++)] = pt;


	return 0;

}